package main

import "fmt"

func main() {

	fmt.Println(fib2(4))
}
func fib(N int) int {

	if N == 0 {
		return 0
	}
	if N == 1 {
		return 1
	}

	return fib(N-1) + fib(N-2)
}

func fib2(N int) int {

	if N <= 1 {
		return 1
	}

	nums := make([]int, 10)
	nums[0] = 0
	nums[1] = 1
	for i := 2; i <= N; i++ {
		nums[i] = nums[i-1] + nums[i-1]
	}
	return nums[N]
}
